package Array_and_String;
/*
对角线遍历
给你一个大小为 m x n 的矩阵 mat ，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。
示例 1：
输入：mat = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,4,7,5,3,6,8,9]
示例 2：
输入：mat = [[1,2],[3,4]]
输出：[1,2,3,4]
作者：LeetCode
链接：https://leetcode.cn/leetbook/read/array-and-string/cuxq3/
 */

public class _23对角线遍历 {
    public static void main(String[] args) {

        int[][] n = {{1,2,3},{4,5,6},{7,8,9}};

        int[] order = findDiagonalOrder(n);

        for (int i : order) {
            System.out.print(i);
        }


    }

    public static int[] findDiagonalOrder(int[][] mat) {
        //将二维数组按对角线层进行遍历
        //层数i = m + n - 1
        int m = mat.length;
        int n = mat[0].length;

        int[] res = new int[m * n];
        int index = 0;
        for (int i = 0; i < m + n - 1; i++) {
            //如果层数为偶数,自下往上遍历
            if (i % 2 == 0) {
                //x + y == i
                int x = i >= m ? m - 1 : i;
                int y = i >= m ? i - m + 1 : 0;
                while (x >= 0 && y < n) {
                    res[index] = mat[x][y];
                    index++;
                    x--;
                    y++;
                }

            } else {
                //如果层数为奇数,自上往下遍历
                int x = i >= n ? i - n + 1 : 0;
                int y = i >= n ? n - 1 : i;
                while (x < m && y >= 0) {
                    res[index] = mat[x][y];
                    index++;
                    x++;
                    y--;
                }
            }
        }
        return res;

    }
}
